package com.LeeCode;

/**
 * 元素和小于等于 k 的子矩阵的数目
 */

public class Code3070 {
    public static void main(String[] args) {

    }

    public int countSubmatrices(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][] preSum = new int[m + 1][n + 1];
        int ans = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                preSum[i+1][j+1] = grid[i][j] + preSum[i+1][j] + preSum[i][j+1] - preSum[i][j];
                if(preSum[i+1][j+1] <= k) ans++;
            }
        }
        return ans;
    }
}
